Rendering inhomogeneous volume densities is a challenging problem. A primary difficulty comes from the inability to analytically importance sample the transmission term:τ(t)=e−∫0t(σs(x)+σa(x))dx  (1)
Where τ(t) is the transmission term, t is the distance along the ray, σs is the scattering coefficient, and σa is the absorption coefficient. That is, heterogeneous media add the complication of a nested integral in the computation of the transmission term, and this integral is dependent on the sample position along the line.
Brute force techniques may be employed to calculate the transmission term. For example, the classical ray marching algorithm has a long history of use in production rendering due to its simplicity. Such is illustrated in prior art FIG. 1. In the system 10 of FIG. 1, a light source 14, shown as a point light source, illuminates an inhomogeneous volume 16 and the scene is incident on a pixel, point, or other such viewpoint 24, representing a point on a camera or the viewer's eye, through a plurality of rays 20 (only one of which is shown for clarity). In this way, once all rays on the camera are combined and the scene is rendered, a viewer receives an image of the inhomogeneous volume 16.
The volume equation is solved by “marching down the ray” in fixed or adaptive steps, evaluating the lighting at each sample point 18. Unfortunately, for each lighting call, shadow rays must themselves be ray marched, shown in FIG. 1 by points 22. The volume is sampled and lighting computed at each of these points as well, leading to a quadratic number n2 of evaluations. In other words, just a single camera ray requires many samples as each additional step adds on the order of n samples. Such evaluations are generally performed by the shader, which is a computer program employed to calculate rendering effects, usually through a graphical processing unit.
Solutions to this problem generally fall into categories of “unbiased” and “biased”.
For example, the classical Woodcock tracking algorithm from nuclear physics is an unbiased solution to this problem. However, it is a rejection sampling algorithm, and as such its performance is highly dependent on the sparsity of the density field. In addition, the algorithm requires computing an upper bound on the extinction coefficient σt, which may be difficult for procedural or out-of-core representations, which are common in production rendering. While improvements on this algorithm have been made, they do not solve the above issues. Moreover, such improvements generally increase memory usage and require the construction of data structures that do not directly support motion blur. In addition, appropriate probability density functions for such situations are generally not directly evaluable.
In certain biased solutions to this problem, light caching techniques such as deep shadow maps have been employed. Unfortunately these techniques require multiple passes, and are prone to many sources of artifacts. In addition, treatment of multiple scattering requires still further approximations.
Stochastic ray marching, as illustrated by histogram 30 in FIG. 1, has also been attempted, where volumes are sampled along rays until such a point as e−τ(t)<ε. Lighting is then computed for each step. Such methods are similar to unbiased algorithms, but are still biased due to the fixed size of the steps. In such techniques the sample distribution is only implicit, and the probability density function is not directly evaluable.
Hence, there remains a need for a rendering technique for inhomogeneous participating media which can compute lighting through such media without the disadvantages noted above.